#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

TreeNode* tree_builder(const std::vector<int>& data) 
{
    // 等于等于-1其实不用返回
    if (data.empty() || data[0] == -1) return nullptr;
    
    // 创建待加入节点
    TreeNode* root = new TreeNode;
    root->left = nullptr;
    root->right = nullptr;
    root->val = data[0];

    // 创建队列用于真正层序遍历
    std::queue<TreeNode*> q;
    q.push(root);

    // i 是计数器，用来进行迭代计数器
    int i = 1;

    while (!q.empty() && i < data.size()) 
    {
        // 惯用手法
        TreeNode* node = q.front();
        q.pop();    // 标记完直接pop毫不留情
        
        // 构建左子树
        if (i < data.size() && data[i] != -1) 
        {
            TreeNode*new_node = new TreeNode;
            new_node->left = nullptr;
            new_node->right = nullptr;
            new_node->val = data[i];
            node->left = new_node;
            q.push(node->left);
        }
        i++;
        
        // 构建右子树
        if (i < data.size() && data[i] != -1) 
        {
            // 直接一步把节点放上去？？？
            // 但是这个部分，由于我没有写构造函数的习惯
            // 因此我只能像构造链表那样两步走
            TreeNode*new_node = new TreeNode;
            new_node->left = nullptr;
            new_node->right = nullptr;
            new_node->val = data[i];
            node->right = new_node;
            q.push(node->right);
        }
        i++;
    }
    
    // 最后返回，然后你发现其实你一直都没有进行内存释放
    return root;
}

// 接下来接续一个之字形输出那就太完美了 
void zig_zag(TreeNode*root)
{
    // 首先还是判空
    if (!root)
    {
        return ;
    }

    // 依旧新层序遍历
    std::vector<std::vector<int>>zz_vector;
    std::queue<TreeNode*>q;
    q.push(root);

    // 你看这里的q.push(root)就是提前往里放入了一个节点作为下一次的待遍历节点
    while (!q.empty())
    {
        // 记录即将遍历的个数以控制遍历次数
        int n = q.size();
        std::vector<int>temp;

        while (n--)
        {
            TreeNode*here = q.front();
            q.pop();
            if(here)
            {
                // 这里其实push进队列前可以进行一下判断啦
                q.push(here->left);
                q.push(here->right);
                temp.push_back(here->val);
            }
        }

        // 最后完美将temp push进zz_vector
        zz_vector.push_back(temp);
    }

    // 接下来遍历整个二维矩阵
    // 根据奇偶性决定是否倒序遍历
    int k = zz_vector.size();
    for (int i = 0;i < k;i++)
    {
        if (i&1)
        {
            std::reverse(zz_vector[i].begin(),zz_vector[i].end());
            for (auto j :zz_vector[i])
            {
                std::cout<<j<<" ";
            }
            std::cout<<"\n";
        }
        else 
        {
            for (auto j :zz_vector[i])
            {
                std::cout<<j<<" ";
            }
            std::cout<<"\n";
        }
    }
}

int main()
{
    std::vector<int>nodes = {3,9,20,15,7};
    TreeNode*root = tree_builder(nodes);

    // 准备zig zag 输出
    zig_zag(root);
    return 0;   
}